/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/can-place-flowers
   @Language: C++
   @Datetime: 19-05-14 17:07
   */

class Solution {
public:
	/**
	 * @param flowerbed: an array
	 * @param n: an Integer
	 * @return: if n new flowers can be planted in it without violating the no-adjacent-flowers rule
	 */
	bool canPlaceFlowers(vector<int> &flowerbed, int n) {
		// Write your code here
		int head=0, mid=0, tail=0, i=0, j=flowerbed.size();
		for(head=i=0; i<flowerbed.size() && flowerbed[i]==0; ++head, ++i);
		for(tail=0, j=flowerbed.size()-1; j>-1 && flowerbed[j]==0; ++tail, --j);
		if(i>=j) return (head+1)/2>=n;
		n-=head/2+tail/2;
		if(n<1) return true;
		for(mid=0; i<=j; ++i){
			if(flowerbed[i]==0) ++mid;
			else{
				n-=(mid-1)/2;
				mid=0;
				if(n<1) return true;
			}
		}
		return false;
	}
};
